#include<stdio.h>
#include<stdlib.h>
#include<string.h>

typedef struct queue_linklist
{
    struct queue_linklist * next;
    struct queue_linklist * previous;
    int value;
}Node;

static Node * Node_struction(int value){

    Node * node = malloc(sizeof(Node));
    if(NULL == node){

        return NULL;
    }
    node->value = value;
    node->next = NULL;
    node->previous = NULL;

    return node;
}

static Node * queueList_insert(Node * head,int value){

    Node * node = Node_struction(value);
    // -must check (虽然一般不会malloc失败)
    if(NULL == node){

        return head;
    }
    // -must check
    if(NULL == head){

        return node;
    }
    // -升序排序
    // -如果头节点大于value（这里可以使用等号）
    if(head->value >= node->value){

        node->next = head;
        head->previous = node;
        return node;
    }
    Node * ptr = head;
    // -需要ptr来获取下一个节点和上一个节点 所以要保证最后的
    // -可以保证ptr不为NULL
    while(ptr->next && ptr->next->value <= node->value){

        ptr = ptr->next;
    }
    // -插入到最后 并把node->previous指向ptr
    if(NULL == ptr->next){

        ptr->next = node;
        node->previous = ptr;
    }else{

        // -走到这里是在ptr->next->value大于node->value 所以要插入到ptr和ptr->next之间
        node->next = ptr->next;
        ptr->next->previous = node; 

        node->previous = ptr;
        ptr->next = node;
    }
    return head;
}

static Node * queueList_delete(Node * head,int value){

    if(NULL == head){

        return NULL;
    }
    if(head->value == value){

        if(NULL!=head->next){

            head = head->next;
            free(head->previous);
            return head;
        }
        // -only one node
        free(head);
        return NULL;
    }
    Node * ptr = head;
    while(ptr->next && ptr->next->value!=value){

        ptr = ptr->next;
    }
    // -found it 
    if(NULL!=ptr->next){

        // -删除ptr->next节点
        Node * tmp = ptr->next;
        ptr->next = ptr->next->next;
        ptr->next->previous = ptr;
        free(tmp);
    }
    return head;
}

static void queueList_print(Node * head){

    Node * ptr = head;
    while (NULL!=ptr)
    {
        printf("%d ",ptr->value);
        ptr = ptr->next;
    }
    printf(".\n\n");
}

static void queueList_destory(Node * head){

    Node * ptr = NULL;
    while(NULL!=head){

        ptr = head;
        head = head->next;
        free(ptr);
    }
}

// -test examples
int main(int argc,char * argv[]){

    Node * head = NULL;
    head = queueList_insert(head,100);
    head = queueList_insert(head,110);
    head = queueList_insert(head,110);
    head = queueList_insert(head,110);
    head = queueList_insert(head,110);
    head = queueList_insert(head,110);
    head = queueList_insert(head,110);
    head = queueList_insert(head,110);
    head = queueList_insert(head,110);
    head = queueList_insert(head,110);
    head = queueList_insert(head,110);
    head = queueList_insert(head,103);
    head = queueList_insert(head,102);
    head = queueList_insert(head,106);
    head = queueList_insert(head,106);
    head = queueList_insert(head,106);
    head = queueList_insert(head,106);
    head = queueList_insert(head,106);
    head = queueList_insert(head,106);
    head = queueList_insert(head,106);
    head = queueList_insert(head,106);
    head = queueList_insert(head,106);
    head = queueList_insert(head,106);
    head = queueList_insert(head,106);
    head = queueList_insert(head,106);
    head = queueList_insert(head,106);
    head = queueList_insert(head,104);
    head = queueList_insert(head,1012);
    head = queueList_insert(head,1012);
    head = queueList_insert(head,1012);
    head = queueList_insert(head,1012);
    head = queueList_insert(head,1012);
    head = queueList_insert(head,1012);
    head = queueList_insert(head,1012);
    head = queueList_insert(head,1012);
    head = queueList_insert(head,1012);
    head = queueList_insert(head,1012);
    head = queueList_insert(head,1012);
    head = queueList_insert(head,3012);

    queueList_print(head);

    head = queueList_delete(head,104);
    head = queueList_delete(head,106);

    queueList_print(head);
    queueList_destory(head);
    return EXIT_SUCCESS;
}
